package com.wdc.heap;


import com.wdc.queue.Arr;

import java.util.Arrays;

//动态实现大顶堆小顶堆
public class Heap {

    int[] array;
    int size;
    boolean max;

    public int getSize() {
        return size;
    }

    public Heap(int capacity ,boolean max){
        this.array = new int[capacity];
        this.max = max;
    }


    public Heap(int[] array){
        this.array = array;
        this.size = array.length;
        heapify();
    }

    //建堆
    @SuppressWarnings("all")
    public void heapify(){
        //找到最后一个非叶子节点，向前依次下潜
        for(int i = size/2 - 1; i>= 0;i--){
            down(i);
        }

    }

    public boolean isEmpty(){
        return size == 0;
    }

    public boolean isFull(){
        return size == array.length;
    }

    public int peek(){return array[0];}

    /**
     * 向尾部添加元素
     * @param offered
     * @return
     */
    public void offer(int offered){
        if (size == array.length){
            //扩容
            grow();
        }

//        array[size++] = offered;

        up(offered);
        size++;

    }

    private void grow(){
      int capacity = size + (size >> 1);
      int[] newArray = new int[capacity];
      System.arraycopy(array,0,newArray,0,size);
      array = newArray;


    }


    /**
     * 上浮操作
     * @param offered 向尾部添加的元素
     */
    private void up(int offered){
        int child = size;
        while (child > 0){
            int parent = (child -1) / 2;
            //判断是什么堆，来执行相应的上浮操作
            boolean temp = max ? offered > array[parent] : offered < array[parent];
            if (temp ){
                array[child] = array[parent];
            }else {
                break;
            }
            child = parent;

        }
        array[child] = offered;

    }

    public int poll(){
        //先记录要弹出的arr[0]
        int polled = array[0];
        //弹出元素，交换首尾元素，szie -- 实现弹出
        swap(0,size - 1);
        size--;
        //弹出过后根据max 的真值判断是大顶堆还是小顶堆，然后执行堆顶元素的下潜操作
        down(0);
        return polled;
    }


    /**
     * 元素下潜
     * @param parent  下潜元素索引
     */
    private void down(int parent){
        //判断是大顶堆还是小顶堆，并执行相应下潜操作
        //先找到左右孩子
        int left = parent * 2 + 1;
        int right = left + 1;
        int maxOrMin = parent;
        if ((max ? array[left] > array[maxOrMin] : array[left] < array[maxOrMin] )&& left < size){
            maxOrMin = left;
        }
        if ((max ? array[right] > array[maxOrMin] : array[right] < array[maxOrMin] ) && right < size){
            maxOrMin = right;
        }
        //
        if (maxOrMin != parent){
            swap(maxOrMin,parent);
            down(maxOrMin);
        }


    }

    /**
     * 删除指定索引处元素
     * @param index 索引
     * @return 被删除元素
     */
    public int poll(int index) {
        int deleted = array[index];
        up(index);
        poll();
        return deleted;
    }


    private void swap(int i ,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;

    }




    public static void main(String[] args) {
        Heap left = new Heap(7, true);
        Heap right = new Heap(7, false);
        for (int i = 1; i <= 10; i++) {
            left.offer(i);
            right.offer(i);
            System.out.println(Arrays.toString(left.array)+Arrays.toString(right.array));
        }
    }




}
